package com.linyaonan.leetcode.medium._105;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: Lin
 * @date: 2020/1/18
 */
public class ConstructBinaryTree2 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {

            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, inorderMap);
    }

    private TreeNode buildTreeHelper(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd, Map<Integer, Integer> inorderMap) {

        if (pStart == pEnd) {

            return null;
        }

        TreeNode root = new TreeNode(preorder[pStart]);
        int i_root_idx = inorderMap.get(preorder[pStart]);
        int leftLength = i_root_idx - iStart;
        root.left = buildTreeHelper(preorder, pStart + 1, pStart + leftLength + 1, inorder, iStart, i_root_idx, inorderMap);
        root.right = buildTreeHelper(preorder, pStart + leftLength + 1, pEnd, inorder, i_root_idx + 1, iEnd, inorderMap);

        return root;
    }
}
